from typing import List


class Solution:
    """
    方法：使用回溯算法解决N皇后问题
    
    Args:
        n: int - 棋盘的大小和皇后的数量
        
    Returns:
        List[List[str]] - 所有合法的N皇后摆放方案，每个方案是一个字符串列表，表示棋盘的一行
        
    Time: O(N!) - 最坏情况下需要尝试所有可能的皇后摆放位置
    Space: O(N^2) - 需要存储棋盘状态和递归调用栈
    """
    def solveNQueens(self, n: int) -> List[List[str]]:
        def backtrack(row, cols, diag1, diag2, path):
            if row == n:
                res.append([''.join(row) for row in path])
                return
            for col in range(n):
                d1, d2 = row - col, row + col
                if not cols[col] and not diag1[d1] and not diag2[d2]:
                    path[row][col] = 'Q'
                    cols[col] = diag1[d1] = diag2[d2] = True
                    backtrack(row + 1, cols, diag1, diag2, path)
                    path[row][col] = '.'  # 回溯
                    cols[col] = diag1[d1] = diag2[d2] = False

        res = []
        empty_board = [['.'] * n for _ in range(n)]
        cols = [False] * n
        diag1 = [False] * (2 * n - 1)  # 主对角线：row - col ∈ [-(n-1), n-1]
        diag2 = [False] * (2 * n - 1)  # 副对角线：row + col ∈ [0, 2n-2]
        backtrack(0, cols, diag1, diag2, empty_board)
        return res